//https://leetcode.cn/problems/top-k-frequent-words/


class Solution {
public:
    typedef pair<string,int> PSI;
    struct Com
    {
        bool operator()(PSI& a,PSI& b)
        {
            //当频率相同，按字典序排序，即大根堆
            if(a.second==b.second)
                return a.first<b.first;
            //不同，则小根堆
            return a.second>b.second;
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        vector<string> strs(k);
        //1. 预处理
        unordered_map<string,int> hash;
        for(auto& x:words) 
            hash[x]++;
        //2. 建k个大小的最小堆
        priority_queue<PSI,vector<PSI>,Com> minheap;
        for(auto& x:hash)
        {
            minheap.push(x);
            if(minheap.size()>k)
                minheap.pop();
        }

        for(int i=k-1;i>=0;i--)
        {
            strs[i]=minheap.top().first;
            minheap.pop();
        }
        return strs;
    }
};